The previous slide questioned if a "shortsighted" greedy approach could guarantee a globally optimal MST. The surprising answer is yes, and the reason lies in a powerful theorem known as the cut property. This property provides the theoretical justification for why greedy MST algorithms work.

  • A cut is a partition of the vertices $V$ of a graph into two disjoint, non-empty sets, let's call them $S$ and $T$.
  • A crossing edge is any edge $(u, v)$ that connects a vertex in set $S$ to a vertex in set $T$.
  • The cut property states: For any cut in the graph, the crossing edge with the smallest weight (the "light edge") is safe. This means this edge must be part of at least one of the graph's Minimum Spanning Trees.
  • This is the key insight: by repeatedly finding a cut and adding its minimum-weight crossing edge, we are guaranteed to be making a correct step. We can never go wrong by greedily choosing a safe edge.

The Cut Property

Let $G = (V, E)$ be a connected, weighted, undirected graph. A cut is any partition of $V$ into two non-empty, disjoint sets $S$ and $T = V - S$. If $e = (u, v)$ is an edge with $u$ in $S$ and $v$ in $T$, and $w(u, v)$ is less than or equal to the weight of any other edge crossing the cut, then $e$ belongs to some Minimum Spanning Tree of $G$.